class Solution:
  def fib(self, n: int) -> int:
    if n == 0:
      return 0
    if n == 1:
      return 1
    fib_list = [0, 1]
    for i in range(2, n+1):
      fib_list.append(fib_list[i-1] + fib_list[i-2])
      # print('fib_list[{}]={}'.format(i, fib_list[i]))
    return int(fib_list[i] % 1000000007)


'''
STATUS: SOLVED
TRIES:  2
TIME:   36 MS
MEMORY: 13.6 MB
'''
if __name__ == "__main__":
    solution = Solution()
    print(solution.fib(81))